package solvers.shortestPathTree;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


import controller.solvers.*;
import java.util.Vector;
import jgf.Arc;
import jgf.Attribute;
import jgf.IGraph;
import jgf.Node;
import jgf.exceptions.arc.BadArcInsertionException;
import jgf.lists.Digraph;

/**
 *
 * @author Biddu
 */
public class ShortestPathTree implements ISolver{

    /**
     * The class SPT implements Dijkstra's Algorithm for SPT.
     * For a given Acyclic Graph the logic below finds the shortest path.
     * This has little limitation like Number of Nodes should
     * not exceed 10000 beacuse for this program infinity is 10000
     */
    public static String ARC_ATTRIBUTE = "COST";
    public static final String NODE_ATTRIBUTE_SPT = "weight";
    public static final int ROOT_WEIGHT = 0;
    public static final int INFINITY = Integer.MAX_VALUE;




    /**
     * For a given Vector of Input Nodes it finds the
     * Node which has the minimum weight.
     * @param inputNodes
     * @return
     */
    private static Node minimumNode(Vector<Node> inputNodes) {
        Node minNode = new Node();
        int minWeight = INFINITY;
        for (int n = 0; n < inputNodes.size(); n++) {
            int temp = inputNodes.get(n).getAttribute(NODE_ATTRIBUTE_SPT).getValue();
            if (temp < minWeight) {
                minWeight = temp;
                minNode = inputNodes.get(n);
            }
        }
        return minNode;
    }

    private static String validateInputData(IGraph input){
        String ret = null;
        if((input == null)){
            ret = "Graph Not Defined";
        }
		else if(!(input instanceof Digraph)){
            ret = "Graph is not a Di-Graph";
        }
		else if(input.getNodeList().size()<1){
            ret = "There is no Node";
        }
		else if(input.getArcList().size()<1){
            ret = "There are no Arcs";
        }
        else if(input.getSources() == null){
            ret = "Source not Set";
        }
		else if(!(input.getArcAttributes().containsKey("COST")||input.getArcAttributes().containsKey("cost"))){
            ret = "Create ARC Attribute in the Rules , SPT uses COST/cost on the ARCS";
        }
        return ret;
    }

    private static int getAttributeValue(Vector<Attribute> input, String attributeName){
        int retVal = Integer.MIN_VALUE;
        try{
            for(Attribute attr : input){
                if(attr.getName().equals(attributeName)){
                    retVal = attr.getValue();
                }
            }
        }catch(NullPointerException ne){
            //WTF why send a null stuff
            //Possible objects is input
        }
        return retVal;
    }

    /**
     * Takes the directed Graph as input and the Root Node element and return the
     * SPT
     * @param input
     * @param root
     * @return
     */

    //Finally I have written a complicated algorithm..hopefully I will understand it later

    public IGraph solve (IGraph input)throws UnappropriateTypeException{
        try{
            String errMsg = validateInputData(input);
            if(!(errMsg==null)){//If no return message means validation passed
                throw new UnappropriateTypeException(errMsg);
            }
            Node root = new Node(input.getSources().getIndex(), input.getSources().getLabel(), input.getSources().getAttributes());
            boolean negARC = false;
            Vector<Arc> forwardStar = new Vector<Arc>();
            Vector<Node> currentNodes = new Vector<Node>();//Q
            Vector<Digraph> output = new Vector<Digraph>();
            Digraph tempGraph = new Digraph();
            //tempGraph input.clone();
            for(Node node : input.getNodeList()){
                Node tempNode = new Node(node.getId(),node.getLabel() , node.getAttributes());
                tempGraph.insertNode(tempNode);
            }
            for (Node node: tempGraph.getNodeList()) {
                Vector<Attribute> attr = null;
                if (node.getId() == root.getId()) {
                    if(node.getAttributes()!=null){
                        attr = node.getAttributes();
                    }else{
                        attr = new Vector<Attribute>();
                        node.setAttributes(attr);
                    }
                    Attribute at = new Attribute(NODE_ATTRIBUTE_SPT,ROOT_WEIGHT);
                    attr.add(at);
                    currentNodes.add(node);
                    tempGraph.setSource(node);
                } else {
                    if(node.getAttributes()!=null){
                        attr = node.getAttributes();
                    }else{
                        attr = new Vector<Attribute>();
                        node.setAttributes(attr);
                    }
                    Attribute at = new Attribute(NODE_ATTRIBUTE_SPT,INFINITY);
                    attr.add(at);
                }
            }
            for(int a=0; a<input.getArcList().size();a++){
                if(input.getArcList().get(a).getAttribute(ARC_ATTRIBUTE).getValue()<0){
                    negARC = true;
                    break;
                }
            }
            while (!currentNodes.isEmpty()) {
                Node selectedNode;
                if (negARC){
                    selectedNode = currentNodes.firstElement();
                }else{
                    selectedNode = minimumNode(currentNodes);
                }
                forwardStar.clear();
                forwardStar = input.getForwardStar(selectedNode.getId());

                for(Arc forwardArc : forwardStar){
                    //Search for the Node in TempGraph whose
                    Node tempNodeTo = null;
                    for(Node node : tempGraph.getNodeList()){
                        if(node.getId()== forwardArc.getTo().getId()){
                            tempNodeTo = node;
                        }
                    }
                    if(tempNodeTo==null){
                        throw new NullPointerException("SPT Solver error. Forward Star of ARC "
                                +forwardArc.getFrom().getId()+"-"+forwardArc.getTo().getId()+"");
                    }
                    if(selectedNode.getAttribute(NODE_ATTRIBUTE_SPT).getValue()
                            + forwardArc.getAttribute(ARC_ATTRIBUTE).getValue()
                                < tempNodeTo.getAttribute(NODE_ATTRIBUTE_SPT).getValue()){
                        
                        tempNodeTo.getAttribute(NODE_ATTRIBUTE_SPT).setValue(selectedNode.getAttribute(NODE_ATTRIBUTE_SPT).getValue()
                                + forwardArc.getAttribute(ARC_ATTRIBUTE).getValue());
                        currentNodes.add(tempNodeTo);

                        for(Arc arc : tempGraph.getArcList()){
                            if(arc.getTo().getId()==forwardArc.getTo().getId()){
                                tempGraph.deleteArc(arc.getFrom(),arc.getTo(),arc.getIndex());
                            }
                        }
                        //Time to add the Arc.
                        Node from = null;
                        Node to = null;
                        for(Node node : tempGraph.getNodeList()){
                            if(node.getId()== forwardArc.getFrom().getId()){
                                from = node;
                            }
                            if(node.getId()== forwardArc.getTo().getId()){
                                to = node;
                            }
                        }
                        Arc tmpArc = new Arc(from,to,forwardArc.getLabel(),null);
                        tempGraph.insertArc(tmpArc);
                        //Now restore the ARC Attribuutes:
                        for (Attribute atr : input.getArc(tmpArc.getFrom(), tmpArc.getTo(), tmpArc.getIndex()).getAttributes()) {
                            tmpArc.addAttribute(atr.getName(),atr.getValue());
                        }
                        output.add(tempGraph);
                    }
                }
                currentNodes.remove(selectedNode);
            }
            //Restore some basic things like the List of
            //Node and Arc attributes from the Input Graph.
            output.lastElement().setArcAttributes(input.getArcAttributes());
            output.lastElement().setNodeAttributes(input.getNodeAttributes());
            //Time to remove NODE_ATTRIBUTE_SPT from the nodes.
            for (Node node : output.lastElement().getNodeList()){
                node.removeAttribute(NODE_ATTRIBUTE_SPT);
            }
            return output.lastElement();
        }catch(Exception ex){//Catch all sorts of Exception raised in the program
            ex.printStackTrace();
            throw new UnappropriateTypeException(ex.getMessage());
        }
    }

    public static void main(String[] s)throws BadArcInsertionException{
        Vector<Attribute> attrs = new Vector<Attribute>();
        attrs.clear();
        Attribute attr= null;
        IGraph graph = new Digraph();
        Node node1 = new Node();
        graph.insertNode(node1);
        Node node2 = new Node();
        graph.insertNode(node2);
        Node node3 = new Node();
        graph.insertNode(node3);
        Node node4 = new Node();
        graph.insertNode(node4);
        Node node5 = new Node();
        graph.insertNode(node5);
        Node node6 = new Node();
        graph.insertNode(node6);
        Node node7 = new Node();
        graph.insertNode(node7);

        Arc arc12 = new Arc(graph.getNode(1), graph.getNode(2), "1-2");
        attr = new Attribute(ARC_ATTRIBUTE, 3);
        arc12.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc12);

        Arc arc13 = new Arc(graph.getNode(1), graph.getNode(3), "1-3");
        attr = new Attribute(ARC_ATTRIBUTE, 4);
        arc13.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc13);

        Arc arc14 = new Arc(graph.getNode(1), graph.getNode(4),"1-4");
        attr = new Attribute(ARC_ATTRIBUTE, 5);
        arc14.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc14);

        Arc arc24 = new Arc(graph.getNode(2), graph.getNode(4),"2-4");
        attr = new Attribute(ARC_ATTRIBUTE, -1);
        arc24.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc24);

        Arc arc26 = new Arc(graph.getNode(2), graph.getNode(6),"2-6");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc26.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc26);

        Arc arc27 = new Arc(graph.getNode(2), graph.getNode(7),"2-7");
        attr = new Attribute(ARC_ATTRIBUTE, 3);
        arc27.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc27);

        Arc arc32 = new Arc(graph.getNode(3), graph.getNode(2),"3-2");
        attr = new Attribute(ARC_ATTRIBUTE, 6);
        arc32.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc32);

        Arc arc34 = new Arc(graph.getNode(3), graph.getNode(4),"3-4");
        attr = new Attribute(ARC_ATTRIBUTE, 5);
        arc34.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc34);

        Arc arc36 = new Arc(graph.getNode(3), graph.getNode(6),"3-6");
        attr = new Attribute(ARC_ATTRIBUTE, -1);
        arc36.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc36);

        Arc arc37 = new Arc(graph.getNode(3), graph.getNode(7),"3-7");
        attr = new Attribute(ARC_ATTRIBUTE, 5);
        arc37.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc37);

        Arc arc45 = new Arc(graph.getNode(4), graph.getNode(5),"4-5");
        attr = new Attribute(ARC_ATTRIBUTE, -6);
        arc45.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc45);

        Arc arc53 = new Arc(graph.getNode(5), graph.getNode(3),"5-3");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc53.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc53);

        Arc arc65 = new Arc(graph.getNode(6), graph.getNode(5),"6-5");
        attr = new Attribute(ARC_ATTRIBUTE, 2);
        arc65.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc65);

        Arc arc76 = new Arc(graph.getNode(7), graph.getNode(6),"7-6");
        attr = new Attribute(ARC_ATTRIBUTE, -1);
        arc76.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc76);

        ShortestPathTree spt = new ShortestPathTree();
        System.out.println("Before Solving: ");
        for(Arc arc: graph.getArcList()){
            System.out.println("Arc: "+arc.getLabel());
        }
        try {
            graph.setSource(graph.getNode(1));
            graph = spt.solve(graph);
        } catch (UnappropriateTypeException ex) {
            //Logger.getLogger(ShortestPathTree.class.getName()).log(Level.SEVERE, null, ex);
            System.out.println("Nothing"+ex.getMessage());
        }
        System.out.println("After Solving: ");
        for(Arc arc: graph.getArcList()){
            System.out.println("Arc: "+arc.getLabel());
        }

        /*Vector<Attribute> attrs = new Vector<Attribute>();
        attrs.clear();
        Attribute attr= null;
        IGraph graph = new Digraph();
        Node node1 = new Node();
        graph.insertNode(node1);
        Node node2 = new Node();
        graph.insertNode(node2);
        Node node3 = new Node();
        graph.insertNode(node3);
        Node node4 = new Node();
        graph.insertNode(node4);
        Node node5 = new Node();
        graph.insertNode(node5);
        Node node6 = new Node();
        graph.insertNode(node6);
        Node node7 = new Node();
        graph.insertNode(node7);

        Arc arc12 = new Arc(node1, node2, "1-2");
        attr = new Attribute(ARC_ATTRIBUTE, 4);
        arc12.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc12);

        Arc arc13 = new Arc(node1, node3, "1-3");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc13.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc13);

        Arc arc24 = new Arc(node2, node4,"2-4");
        attr = new Attribute(ARC_ATTRIBUTE, 3);
        arc24.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc24);

        Arc arc32 = new Arc(node3, node2,"3-2");
        attr = new Attribute(ARC_ATTRIBUTE, 2);
        arc32.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc32);

        Arc arc35 = new Arc(node3, node4,"3-5");
        attr = new Attribute(ARC_ATTRIBUTE, 9);
        arc35.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc35);

        Arc arc36 = new Arc(node3, node6,"3-6");
        attr = new Attribute(ARC_ATTRIBUTE, 4);
        arc36.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc36);

        Arc arc43 = new Arc(node4, node3,"4-3");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc43.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc43);

        Arc arc45 = new Arc(node4, node5,"4-5");
        attr = new Attribute(ARC_ATTRIBUTE, 2);
        arc45.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc45);

        Arc arc52 = new Arc(node5, node2,"5-2");
        attr = new Attribute(ARC_ATTRIBUTE, 0);
        arc52.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc52);

        Arc arc56 = new Arc(node5, node6,"5-6");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc56.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc56);

        Arc arc64 = new Arc(node6, node4,"6-4");
        attr = new Attribute(ARC_ATTRIBUTE, 1);
        arc64.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc64);

        Arc arc67 = new Arc(node6, node7,"6-7");
        attr = new Attribute(ARC_ATTRIBUTE, 2);
        arc67.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc67);

        Arc arc75 = new Arc(node7, node5,"7-5");
        attr = new Attribute(ARC_ATTRIBUTE, 2);
        arc75.addAttribute(attr);//setAttributes(attrs);
        graph.insertArc(arc75);

        ShortestPathTree spt = new ShortestPathTree();
        System.out.println("Before Solving: ");
        for(Arc arc: graph.getArcList()){
            System.out.println("Arc: "+arc.getLabel());
        }
        try {
            graph = spt.solve(graph, node1);
        } catch (UnappropriateTypeException ex) {
            //Logger.getLogger(ShortestPathTree.class.getName()).log(Level.SEVERE, null, ex);
            System.out.println("Nothing");
        }
        System.out.println("After Solving: ");
        for(Arc arc: graph.getArcList()){
            System.out.println("Arc: "+arc.getLabel());
        }*/
    }

    public IGraph step() {
        throw new UnsupportedOperationException("Not supported yet.");
    }
}
